/**第105题*/
//根据一棵树的前序遍历与中序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
// Related Topics 树 深度优先搜索 数组 
// 👍 822 👎 0

package tree.leetcode.editor.cn;

import com.dq.tree.TreeNode;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
    }
        //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {

        if(preStart>preEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        //在中序遍历中查找根节点的index
        int rootIndex = inStart-1;
        while(inorder[++rootIndex]!=preorder[preStart]);
        //中序新区间为[instart, rootIndex-1], [rootIndex+1,inend]
        //前序新区间为[prestart+1, rootIndex-instart + prestart]
        //[rootIndex-instart + prestart+1,preEnd]
               root.left = buildTree(preorder, inorder,
                preStart+1, rootIndex-inStart+preStart,
                inStart,rootIndex-1);
        root.right = buildTree(preorder,inorder,
                rootIndex-inStart+preStart+1,preEnd,
                rootIndex+1,inEnd);

        return root;
    }
    //[start, end]
    public int index(int[] nums, int start, int end, int target){

        int index = start-1;
        while(nums[++index]!=target);
        return index;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}